#leetcode题目95：不同的二叉搜索树II
#难度：中等


#TODO 没太看懂，后面再看。

from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def generate(start, end):
            if start > end:
                return [None,]
            allTrees = []
            for i in range(start, end+1):
                leftTrees = generate(start, i-1)
                rightTrees = generate(i+1, end)
                for l in leftTrees:
                    for r in rightTrees:
                        curTree = TreeNode(i)
                        curTree.left = l
                        curTree.right = r
                        allTrees.append(curTree)
            return allTrees
        return generate(1,n) if n else []


#测试数据
def print_tree(root, level=0):
    if root is None:
        return
    print("  " * level + str(root.val))
    print_tree(root.left, level + 1)
    print_tree(root.right, level + 1)

n = 3
solution = Solution()
trees = solution.generateTrees(n)
print(f"n={n}时，共有{len(trees)}种不同的二叉搜索树：")
for i, tree in enumerate(trees):
    print(f"树{i+1}:")
    print_tree(tree)
    print()
